數據結構（C語言描述）（第2版）[陳明主編書籍]

《數據結構》是2011年11月1日清華大學出版社出版的圖書，作者是陳明。

內容簡介

本書系統地介紹了各種典型的數據結構，主要包括算法、線性表、棧和佇列、串、數組、樹、圖、查找、排序、遞歸和檔案；   為了加強對算法的理解，也介紹了算法分析方面的內容。本書語言精練、概念清楚、注重實用、邏輯性強，各章中所涉及的數據結構與算法都給出了C語言描述，並附有大量習題，便於學生理解與掌握。本書可作為高等院校計算機專業及相關專業的教材，也可作為計算機套用技術人員的參考書  

目錄

第1章 緒論1

1.1 問題的提出1

1.2 基本術語2

1.3 數據結構的概念4

1.4 數據的邏輯結構6

1.5 數據的存儲結構7

1.6 數據的運算9

1.7 數據的邏輯結構、存儲結構及運算的關係9

1.8 算法概述10

1.8.1 算法與算法特性10

1.8.2 算法描述10

1.9 算法分析11

小結13

習題114

第2章 線性表15

2.1 線性表的定義與運算15

2.1.1 線性表的定義15

2.1.2 線性表的運算16

2.2 線性表的順序存儲19

2.2.1 順序存儲19

2.2.2 順序結構線性表的運算20

2.2.3 順序存儲結構的優點23

2.2.4 順序存儲結構的缺點23

2.3 線性表的鏈式存儲23

2.3.1 線性鍊表23

2.3.2 線性鍊表的運算26

2.3.3 靜態鍊表312.3.4 靜態鍊表的運算31

2.3.5 循環鍊表32

2.3.6 循環鍊表的運算33

2.3.7 雙向鍊表 34

2.3.8 雙向鍊表的運算35

2.3.9 鏈式存儲結構的特點37

2.4 鏈式存儲結構的套用37

2.4.1 約瑟夫問題37

2.4.2 一元多項式求和39

2.4.3 在集合方面的套用42

小結44

習題244  

第3章棧和佇列46

3.1棧46

3.1.1棧的定義46

3.1.2棧的順序存儲結構47

3.1.3棧的鏈式存儲結構51

3.1.4順序棧和鏈式棧的比較53

3.2棧的套用53

3.2.1迷宮問題53

3.2.2算術表達式求值56

3.2.3子程式的調用和返回59

3.2.4數制轉換60

3.3佇列61

3.3.1佇列的定義61

3.3.2佇列的順序存儲62

3.3.3佇列的鏈式存儲68

3.3.4優先佇列72

3.4佇列的套用73

3.4.1設備速度不匹配問題73

3.4.2舞伴問題73

小結75

習題375

第4章串77

4.1串的基本概念77

4.2串的存儲結構78

4.2.1串的靜態存儲結構79

4.2.2串的動態存儲結構80

4.3串的基本運算及實現82

4.3.1串的基本運算82

4.3.2實現串的基本運算的算法83

4.4模式匹配87

4.4.1BF算法87

4.4.2KMP算法90

小結94

習題494

第5章數組96

5.1數組的概念96

5.1.1數組的定義及基本操作96

5.1.2抽象數據類型數組的定義98

5.2數組的順序存儲結構98

5.3矩陣的壓縮存儲102

5.3.1特殊矩陣的壓縮存儲102

5.3.2稀疏矩陣的壓縮存儲104

小結118

習題5118

第6章樹120

6.1樹120

6.1.1樹的定義120

6.1.2樹的表示方法121

6.1.3樹的基本術語121

6.1.4樹的ADT定義122

6.2二叉樹123

6.2.1二叉樹的定義及基本形態123

6.2.2二叉樹的存儲結構125

6.2.3二叉樹的遍歷127

6.3線索二叉樹130

6.3.1二叉樹的線索化131

6.3.2利用線索遍歷131

6.4樹、森林和二叉樹的關係136

6.4.1樹的存儲結構136

6.4.2森林與二叉樹的轉換139

6.4.3樹和森林的遍歷142

6.5哈夫曼樹及其套用143

6.5.1與哈夫曼樹有關的定義143

6.5.2哈夫曼樹的構造145

6.5.3哈夫曼樹的套用146

小結151

習題6151  

第7章圖155

7.1圖的基本概念155

7.2圖的存儲結構159

7.2.1鄰接矩陣160

7.2.2鄰接表162

7.2.3十字鍊表166

7.2.4鄰接多重表167

7.3圖的遍歷169

7.3.1深度優先搜尋169

7.3.2廣度優先搜尋172

7.4生成樹174

7.4.1普里姆（Prim）算法175

7.4.2克魯斯卡爾(kruskal)算法178

7.5最短路徑180

7.5.1單源最短路徑180

7.5.2頂點之間的最短路徑183

7.6拓撲排序184

7.7關鍵路徑188

小結195

習題7195

第8章查找199

8.1基本概念199

8.2線性表的查找200

8.2.1順序查找200

8.2.2折半查找202

8.2.3分塊查找205

8.3樹表的查找208

8.3.1二叉查找樹208

8.3.2平衡二叉樹214

8.3.3B-樹220

8.4哈希表的查找222

8.4.1哈希表222

8.4.2構造哈希表的基本方法223

8.4.3解決衝突的方法225

8.4.4哈希表的查找方法228

8.5查找方法的比較228

小結229

習題8229

第9章排序232

9.1基本概念232

9.2內部排序方法235

9.2.1插入排序235

9.2.2冒泡排序239

9.2.3快速排序240

9.2.4選擇排序243

9.2.5歸併排序248

9.2.6基數排序251

9.3內部排序方法比較256

9.4外部排序方法簡介257

小結257

習題9258

第10章遞歸261

10.1遞歸的定義261

10.2典型遞歸問題262

10.2.1漢諾塔問題262

10.2.2八皇后問題264

10.3遞歸的實現266

10.4遞歸轉化為非遞歸的一般過程270

10.5遞歸的時間和空間複雜度273

小結274

習題10275

第11章檔案276

11.1外存儲器的介紹276

11.2有關檔案的概念277

11.2.1檔案及其類別278

11.2.2檔案的操作279

11.3檔案的組織280

11.3.1順序檔案281

11.3.2索引檔案282

11.3.3散列檔案287

11.3.4多關鍵字檔案289

小結291

習題11291

附錄上機實驗293

參考文獻296